package algorithm.dynamic;

import java.util.HashMap;

/**
 * 数组中最长的连续序列
 */
public class LongestConsecutive {
    /**
     * 示例 1 2 3   （当前遍历到的）4        5 6 7
     *  less = 3  more = 4， left = 1 more = 4   len = 4
     *  less = 4  more = 5，left = 1 more = 7  len = 7
     * @param arr
     * @return
     */
    public int longestConsecutive(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int max = 1;
        // key 是arr的元素， value则是长度
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0 ;i < arr.length; i++) {
            if (!map.containsKey(arr[i])) {
                map.put(arr[i], 1);
                // 合并前一个
                if (map.containsKey(arr[i] - 1)) {
                    max = Math.max(max, merge(map, arr[i] - 1, arr[i]));
                }
                // 合并后一个
                if (map.containsKey(arr[i] + 1)) {
                    max = Math.max(max, merge(map, arr[i], arr[i] + 1));
                }
            }
        }
        return max;
    }

    private int merge(HashMap<Integer, Integer> map, int less, int more) {
        int left = less - map.get(less) + 1;
        int right = more + map.get(more) - 1;
        int len = right - left + 1;
        map.put(left, len);
        map.put(right, len);
        return len;
    }

}
